'''
编程思路：
做编程题，思路很重要，没有思路，或者思路不清晰，都就没办法写得出程序，即使写出来了也一定是BUG。
1. 看题目，知道输入和输出的类型
2. 了解输入中有多少种类型的数据  --> 决定至少需要多少个中间变量
'''

from collections import Counter
import time


'''
之字形变换
ABCDEFG 3
思路：  按列存放元素 ---> 列转行
思路2： 利用矩阵的特性，把列元素用行保存，然后转置 --> np.transpose(A)
'''
def Z_change():
    s_in, w = list(input().split())
    w = int(w) # 行

    total_num = len(s_in)   # 字符串字符数
    cols = total_num // w   # 列数
    f_num = total_num % w   # 完整排出几列后多余出来的数

    temp_res = [] # 按列存储
    for i in range(cols): # 不包含余数列的元素
        temp_res.append(s_in[i*w : i*w+w])
        if i % 2:
            temp_res[i] = temp_res[i][::-1] # 奇数列反转

    if f_num: # 多余出来的一列，也要注意是偶数还是奇数列
        if not cols % 2: # 偶数列 # 注意从0开始计数的
            temp_res.append(s_in[total_num-f_num:])
        else: # 奇数列要反转
            s_t = s_in[total_num-f_num:]
            s_t = ' ' * (w - len(s_t)) + s_t[::-1]
            temp_res.append(s_t)

    res = [['']* len(temp_res) for _ in range(w)]  # 创建二维数组记录每个位置的值，没有字符的位置用空字符''表示
    for i in range(len(temp_res)):
        for j in range(len(temp_res[i])):
            res[j][i] = temp_res[i][j]   # 转置
    for i in res:
        output = ''.join(i)
        print(output.rstrip())



'''滑窗，统计一定时间内，窗口中出现的同种颜色最多的车'''
'''
0 1 2 1 1 2 1 1
5
'''
def count_same_car():
    nums = list(map(int, input().split()))
    window_size = int(input())
    ans = 1
    if not nums or not window_size:
        print(0)
    elif len(nums) == 1 or window_size == 1:
        print(1)

    elif len(nums) <= window_size:
        temp001 = nums[:]
        temp002 = Counter(temp001)
        temp003 = sorted(temp002.items(), key=lambda x: x[1])
        print(temp003[-1])
        if temp003:
            ans = max(ans, temp003[-1][1])
        print(ans)
    else:
        for i in range(len(nums)-window_size+1):
            temp001 = nums[i : i+ window_size]
            print(temp001)
            temp002 = Counter(temp001)
            temp003 = sorted(temp002.items(),key=lambda x:x[1])
            # print(temp003)
            if temp003:
                ans = max(ans, temp003[-1][1])
        print(ans)

#-------------------------------------------

'''
明明的随机数，要去掉二进制中包含101的数据
思路：
排列组合的问题
比如：l = 0b100, r = 0b1000000
那么可以先计算0b1000 到0b111111之间含有101的组合数
再分别计算0b100到0b1000之间含有101的数，以及0b111111到0b1000000之间含有101的组合数
f(n) = S(n-1) - f(n-2) + 2^n-3
1. 101      --->    1
2. 1(xxx)   --->    3
3. 1(xxxx)  --->    7 (4 - 1 + 2^2 = 7)
4. 1(xxxxx) --->    16
    4.1. 1(1xxxx) --- 括号内的组合数为7
    4.2. 101(xxx) --- 已经有了101开头了，后续2^3均为符合要求的数，故去掉f(n-2)，加上2^n-3
5. 1(xxxxxx)    --->    1+3+7+16-7+16 = 36
'''

def count_out_nums(num_l, num_r):
    '''穷举法计算num_l, num_r之间有多少个数的二进制形式包含101'''
    cnt = 0
    for i in range(num_l, num_r + 1):
        b_num = bin(i)[2:]
        if '101' in b_num:
            # print(b_num, end=' ')
            cnt += 1
            # if cnt % 10 == 0:
            #     print()
    return cnt

def back(num_end):
    '''统计num_end位二进制数中包含101的组合数'''
    '''这里设计的不行，组合数考虑的不充分'''
    next_len = num_end - 3
    # print(next_len)
    res = 2 ** (next_len) # '101xxx...'的组合情况
    if next_len == 1:
        res += 1
    elif next_len == 2:
        res += 3
    # elif next_len == 3:
    #     res += 8
    elif next_len >= 3: # 还有一些情况没考虑进来
        res += (2 ** (next_len - 1)) -1 # '1101xxx...' 的组合情况
        res += (2 ** (next_len - 2))    # '11101xxx...'的组合情况
        '''3 * back(next_len)
        100101xxx... 
        110101xxx...
        111101xxx...
        '''
        res += 3 * back(next_len)
    return res


def count_bin002(l: int, r: int) -> int:
    '''
    插值法，把00、000、0000等多于一个0往11111里面插
    最后加上111111与111110两个特殊值
    缺少00 与 000等的组合
    '''
    if l > r: return 0

    bin_l = bin(l)[2:] # 最小值
    bin_r = bin(r)[2:] # 最大值

    len_l = len(bin_l) # 最小值长度
    len_r = len(bin_r) # 最大值长度
    res = 0

    if (len_r < 5) or (len_r - len_l < 2):
        res = r - l + 1 - count_out_nums(l, r)

    else:
        if len_l < 3:
            for i in range(3,len_r): # 注意len_r本来就是取不到的，不用-1
                temp = 0
                for j in range(2, i):
                    temp += (i-j)
                res += (temp+2)
            int_l2 = int('11', 2)
            res += int_l2 - l + 1
        else :
            for i in range(len_l+1, len_r):
                temp = 0
                for j in range(2, i):
                    temp += (i-j)
                res += (temp+2)
            int_l2 = int(('1' * len_l), 2)
            res += int_l2 - l + 1 - count_out_nums(l, int_l2)
        int_r1 = int(('1' + '0' * (len_r - 1)), 2)
        res += r - int_r1 + 1 - count_out_nums(int_r1, r)
    print(res)
    return res



l,r = 100, 1000
# l, r = list(map(int, input().split()))
t1 =time.time()
cnt = 0
for i in range(l, r+1):
    b_num = bin(i)[2:]
    if '101' in b_num:
        cnt += 1
print(r - l + 1 - cnt)
t2 = time.time()
print(t2 - t1)

count_bin002(l, r)

'''测试'''
# length = 8
# print(back(length))
# num01 = int(('1'+ '0'*(length-1)), 2)
# num02 = int('1'*length, 2)
# print(count_out_nums(num01, num02+1))



"""
技术二面：
失败了，没能做出来，想的太复杂了
https://leetcode.cn/problems/decode-string/comments/

难点：
1. 在于含有多个切片标准：[、]、数字，因此无法直接用split把字符串切分，
2. 所以思路上，就是遇到这些字符时需要用一个中间列表保存这些值，并进行清零，即手动切片，----> 用栈来缓存中间数据
3. 但是由于数字有独特的作用，需要多用一个变量来承接这个值
"""
from collections import defaultdict

class Solution01:
    '''
    自己的解法思路：
    1. 寻找所有左括号的下标
    2. 当找到一个右括号index2，就拿出最近的一个左括号坐标index1
    3. 把括号内的字符串拿出来，并开始寻找左括号前边的数字（需要翻转）
    4. 把字符串和数字进行相乘
    5. 对原字符串进行置换改动
    6. 字符串变动后长度发生变化，需要手动改变遍历下标重新进行遍历
    '''
    def decodeString(self, s: str) -> str:
        index1 = 0  # 左括号
        index2 = 0  # 右括号
        half = []   # 记录左括号的位置  # 栈
        res = s     # 结果
        temps = ""
        c_r = list(s).count(']')  # 统计右括号的数量，共进行c_r次替换
        num = ""
        i = 0
        while c_r > 0:
            if res[i] == '[':
                half.append(i)

            if res[i] == ']':
                c_r -= 1
                index1 = half.pop()  # 拿出最近的左括号
                index2 = i
                num_index = index1 - 1
                while res[num_index].isdigit():  # 数字可能不只有1位
                    num += res[num_index]
                    num_index -= 1
                num = num[::-1]  # 反转数字
                if num:
                    temps = res[index1 + 1:index2] * int(num)  # 目标内容
                    rep = num + res[index1:index2 + 1]   # 需要被置换的内容  即n[s]
                    num = ""  # 用完后清空
                else:
                    temps = ""
                res = res.replace(rep, temps) # 进行置换
                i = max(0, index1 -len(num) - 1)  # 改动原字符串后，需要修改遍历的下标
            i += 1
        print(res)
        return res

class Solution02:
    '''
    思路很简单，多规则切分，使用 栈 的缓存方式进行切片，
    1. 没遇到 数字 和 [ 就把该字符作为一个结果切片保存到res中
    2. 遇到数字，就用一个中间变量记录下来
    3. 当遇到 [ ，就把切片和数字一起压入栈中, 并进行一次清零操作
    '''
    def decodeString(self, s: str) -> str:
        stack = []  # (str, int) 记录左括号之前的字符串和左括号外的上一个数字
        num = 0
        res = ""  # 实时记录当前可以提取出来的字符串
        for c in s:
            if c.isdigit(): # 数字可能不止个位数，可能是10、100
                num = num * 10 + int(c)
            elif c == "[":
                '''保存前面的值，并清空，就是进行切片'''
                stack.append((res, num))
                res, num = "", 0  # 核心操作，清零，既能保存中间值，又能进行下一次的滑动寻找[]
            elif c == "]":
                top = stack.pop()
                res = top[0] + res * top[1]  # 因为前面做了一次清零操作，所以res就是[]内的字符串
            else:
                res += c  # 记录[]内外的字符 # 清空前是外部的，清空后是内部的
        return res

s_in = "20[leet]"

so = Solution02()
so.decodeString(s_in)


